package com.peng.leetcode.list;


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * MergeKLists
 * <p>
 * 23. 合并K个升序链表
 *
 * @author: lupeng6
 * @create: 2021/2/4 16:58
 */
public class MergeKLists {

    public static void main(String[] args) {
    }



    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        for (ListNode list : lists) {
            if (list != null) {
                q.offer(list);
            }
        }
        ListNode sentry = new ListNode(0);
        ListNode curr = sentry;
        while (!q.isEmpty()) {
            ListNode node = q.poll();
            curr.next = node;
            curr = curr.next;
            if (node.next != null) {
                q.offer(node.next);
            }
        }
        return sentry.next;
    }
}
